package com.lihepeng.leecode.linkedList;


/**
 * leecode 21 合并两个有序的链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
 *
 * @author lihepeng
 */
public class Meger2LinkList {
    /**
     * 使用递归操作完成两个有序链表合并
     *
     * @param l1
     * @param l2
     */
    public ListNode mergefunc1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.value < l2.value) {
            l1.next = mergefunc1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergefunc1(l1, l2.next);
            return l2;
        }

    }

    /**
     * 使用遍历的方式完成合并
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergefunc2(ListNode l1, ListNode l2) {
        ListNode preNode = new ListNode(-1);
        ListNode prev = preNode;
        while (l1 != null && l2 != null) {
            if (l1.value < l2.value) {
                prev.next = l1;
                l1 = l2.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;

        return preNode;
    }

}
